def find(nums):
    """

    Given an array S of n integers, are there elements a, b, c, and d in S
    such that a + b + c + d = target?
    Find all unique quadruplets in the array which gives the sum of target.

    Note:
    Elements in a quadruplet (a,b,c,d) must be in non-descending order.
    (ie, a ≤ b ≤ c ≤ d)
    The solution set must not contain duplicate quadruplets.

    For example, given array S = {1 0 -1 0 -2 2}, and target = 0.

    A solution set is:
    (-1,  0, 0, 1)
    (-2, -1, 1, 2)
    (-2,  0, 0, 2)

    :type nums: List[int]
    :rtype: List[List[int]
    """

    length = len(nums);
    if length < 4:
        print('No enough nums!');
        return None;

    print('Origin:', nums);
    # sort in ascending order
    for i in range(0, length - 1):
        swapped = False;
        for j in range(0, length - i - 1):
            if nums[j] > nums[j + 1]:
                temp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = temp;
                swapped = True;

        if not swapped:
            break;

    # Traverse to find result
    print('Sorted:', nums);
    result = [];
    if nums[0] > 0:
        print('Not found!');
        return None;

    for i in range(0, length - 3):
        if nums[i] > 0:
            break;

        for j in range(i + 1, length - 2):
            sum2 = nums[i] + nums[j];
            if sum2 > 0:
                break;

            for k in range(j + 1, length - 1):
                sum3 = nums[i] + nums[j] + nums[k];
                if sum3 > 0:
                    break;

                for l in range(k + 1, length):
                    sum4 = nums[i] + nums[j] + nums[k] + nums[l];
                    if sum4 > 0:
                        break;
                    elif sum4 == 0:
                        result.append([nums[i], nums[j], nums[k], nums[l]]);
                        break; # ignore duplicates

    print(result);
    return result;



